package class03;

/**
 * 搜索二叉树条件
 * 1. 左树满足
 * 2.右树满足
 * 3.左树最大值小于头节点
 * 4.右树最小值大于头节点
 */
public class Code11_IsBST {


    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }


    public static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean i, int ma, int mi) {
            isBST = i;
            max = ma;
            min = mi;
        }
    }


    public static boolean isBST1(Node head) {
        if (null == head) {
            return true;
        }

        return process(head).isBST;


    }

    static Info process(Node head) {
        if (null == head) {
            //注意此时需要上游判空
            return null;
        }


        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        Integer max = head.value;
        Integer min = head.value;
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }

        boolean isBST = true;
        if (null != leftInfo && !leftInfo.isBST) {
            isBST = false;
        }
        if (null != rightInfo && !rightInfo.isBST) {
            isBST = false;
        }

        if (null != leftInfo && leftInfo.max >= head.value) {
            isBST = false;
        }

        if (null != rightInfo && rightInfo.min <= head.value) {
            isBST = false;
        }

        return new Info(isBST, max, min);
    }

    public static void main(String[] args) {

        Node head = new Node(10);
        head.left = new Node(2);
        head.right = new Node(13);
        head.left.left = new Node(1);
        head.left.right = new Node(5);
        head.right.left = new Node(12);
        head.right.right = new Node(17);
        System.out.println(isBST1(head));


    }

}
